// 逆波兰表达式是一种后缀表达式，运算符写在后面
// 逆波兰表达式主要有以下两个优点：
// 1. 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
// 2. 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

// 思路：堆栈，遇到数字入栈，遇到操作符则取出数进行运算，然后继续入栈，最终结果将在栈的第一个元素
// 时间复杂度：O(n)，n是tokens的长度
// 空间复杂度：O(n)，stack的大小

function evalRPN(tokens) {
    let stack = []
    for (let i = 0; i < tokens.length; i++) {
        if (Number.isNaN(Number(tokens[i]))) {
            let val1 = stack.pop()
            let val2 = stack.pop()
            switch (tokens[i]) {
                case '+':
                    stack.push(val1 + val2)
                    break;
                case '-':
                    stack.push(val1 - val2)
                    break;
                case '*':
                    stack.push(val1 * val2)
                    break;
                case '/':
                    // 这里需要前者除以后者，val1是后者
                    stack.push((val2 / val1)| 0)
                    break;
                default:
                    break;
            }
        } else {
            stack.push(Number(tokens[i]))
        }      
    }
    return stack[0]
}


tokens = ["4","13","5","/","+"]
console.log(evalRPN(tokens))